package str_match

// KMP字符串匹配算法 （核心在于next数组，又称 PrefixTable）
//
// 是一种根据模式串的信息进行匹配的规则，其中找出next数据为关键（用到了DP)
func KMP(text string, pattern string) (result []int) {
	//            subIndex  length
	// -----------------------------
	// text      |  [i]   |   m
	// pattern   |  [j]   |   n
	// -----------------------------
	i, j, m, n := 0, 0, len(text), len(pattern)
	next := PrefixTable(pattern)
	for i < m {
		if j == n-1 && text[i] == pattern[j] {
			result = append(result, i-j)
			j = next[j]
		}
		if text[i] == pattern[j] {
			i++
			j++
		} else {
			j = next[j]
			if j == -1 {
				i++
				j++
			}
		}
	}
	return
}

func PrefixTable(pattern string) []int {
	lps := LongestCommonPrefixAndSuffix(pattern)
	for i := len(lps) - 1; i > 0; i-- {
		lps[i] = lps[i-1]
	}
	lps[0] = -1
	return lps
}

// dp 问题
// opt[i] = opt[i-1] + (if char[opt[i-1]] = char[i] return 1 else return 0)
func LongestCommonPrefixAndSuffix(str string) []int {
	opt := make([]int, len(str))
	for i := range str {
		if i == 0 {
			opt[i] = 0
			continue
		}
		if str[opt[i-1]] == str[i] {
			opt[i] = opt[i-1] + 1
		} else if str[0] == str[i] {
			opt[i] = 1
		} else {
			opt[i] = 0
		}
	}
	return opt
}

func LongestCommonPrefixAndSuffixV2(str string) []int {
	n := len(str)
	l := 0
	opt := make([]int, n)
	opt[0] = 0
	for i := 1; i < n; i++ {
		if str[i] == str[l] {
			l++
			opt[i] = l
		} else {
			l = opt[i-1]
		}
	}

	return opt
}
